The rapid growth of personal computers, the internet, and more recently peer-to-peer services has presented digital content publishers with the challenge of protecting their content from unauthorized copying and redistribution. The ease of distributing digital content via the internet and the sophistication of those making unauthorized copies has created a need for a method which allows publishers to trace unauthorized copies back to one or more persons who produce them.
Publishers today are increasingly distributing their content in digital form, such as MPEG video and mp3 audio. The first challenge that arises when a publisher distributes a digital file or document is that of simple or naïve copying and redistribution. In such a scenario, an authorized purchaser of an electronic file or document makes an exact copy of his file and provides it to another person.
Publishers first fought the challenge of naïve copying and distribution by imbedding digital watermarks into each authorized copy of their content. Each watermark could identify the copyright holder or owner of the document. While watermarking allows a publisher to identify content that it owns, it does little to identify those responsible for unauthorized copying and distribution.
Publishers next used digital fingerprints to stem the tide of unauthorized copying and distribution. A digital fingerprint is a type of watermarking technique in which each copy of an electronic document has information inserted which can uniquely identify the authorized holder of the document. Since inserting a digital fingerprint changes the content of a document, fingerprints need to be small compared to the size of the document so that the authorized copy remains approximately true to the original. Fingerprints that are too large may perceptibly change the color of a digital image or distort the sound of a digital audio file.
A purchaser examining a single fingerprinted copy of an electronic document cannot determine which parts of his document are part of the fingerprint and which parts are not, making removal of the fingerprint difficult. Thus, in the case of naïve copying, a digital fingerprint can be used to trace an electronic document back to its original authorized purchaser. While a digital fingerprint provides a way to combat simple unauthorized copying and distribution, those involved in producing unauthorized copies have become much more sophisticated by acting together.
A group of two or more purchasers acting together may undertake a joint attack on a fingerprinting scheme. As discussed above, a digital fingerprint uniquely identifies a customer based on data inserted into an electronic document which is invisible to the individual purchaser. However, a group of colluding purchasers can compare their copies and determine at which points their copies differ. Since each fingerprint is unique, the points at which the colluders' documents differ reveals parts of their individual fingerprints. Thus, a group of colluding purchasers can compare their copies and use that information to attack or change a fingerprint in an effort to produce a forged fingerprint which is either associated with no purchaser or associated with an innocent purchaser. In either event, the colluders are free to boldly distribute copies with forged fingerprints across today's high-speed networks. Therefore, a method is needed which can identify colluders even after they forge a digital fingerprint.
Currently, prior-art methods exists which allow a publisher to trace a forged fingerprint back to at least one colluding forger. However, these methods produce fingerprints which are too large to be practical when the number of authorized copies distributed is large.
D. Boneh and J. Shaw, in “Collusion-Secure fingerprinting for digital data”, IEEE Trans. Inf. Theory, vol IT-44, no. (5), pp. 1897-1905, 1998, discussed the theoretical background for fingerprints that are c-collusion secure, meaning the fingerprints can trace an unauthorized copy back to at least one member of a group of c colluders with an error of E when there are n authorized purchasers. Boneh and Shaw provided a fingerprinting method where the length of the fingerprint is given by l=32 c4 log(2n/E)log(16 c2 log(2n/E)/E, which generates fingerprints which are unsuitably large when the number of purchasers is large.
Boneh and Shaw also proved the length of a c-collusion secure fingerprinting code cannot be less than the logarithm of the number of fingerprinted copies issued. It would therefore be desirable to have a fingerprinting method which conforms to the lower bound.
Another fingerprinting technique, described in U.S. Pat. No. 6,590,995, uses digital fingerprints based on finite geometric structures. The length of these fingerprints is proportional to the (c+1)st power of the number of customers n and hence is undesirable for a large number of customers.
The present invention provides a c-collusion secure digital fingerprinting method and system which conforms with the lower bound for fingerprint size and is therefore desirable for use as a digital fingerprinting scheme.